In the Sum-of-Subsets problem, there are n positive integers (weights) $w_i$ and a positive integer W. The goal is to find all subsets of the integers that sum to W. As mentioned earlier, we usually state our problems so as to find all solutions.

부분집합의 합을 구하는 문제는 n개의 양의 정수(무게) $w_i$와 양의 정수 W가 주어졌을 때, 합이 W가 되는 정수의 부분집합을 모두 찾는 것이다. n-퀸 문제처럼 모든 해답을 찾도록 알고리즘을 구현할 것이다.

Example Suppose that n = 5, W = 21, and
$$
w_1=5 \quad w_2=6 \quad w_3=10 \quad w_4=11 \quad w_5 = 16.
$$

because
$$
\begin{align}
w_1 + w_2 + w_3 &= 5 + 6 + 10 = 21, \\
w_1 + w_5 &= 5 + 16 = 21, \\
w_3 + w_4 &= 10 + 11 = 21,
\end{align}
$$

Example Suppose that n = 4, W = 13, and
$$
w_1=3 \quad w_2=4 \quad w_3=5 \quad w_4=6.
$$

becasue
$$
\begin{align}
w_1 + w_2 + w_4 = 3 + 4 + 6 = 13
\end{align}
$$
the solutions are {$w_1$, $w_2$, $w_4$}

각 노드에는 그 노드까지의 총 합이 적혀 있다. 가장 왼쪽 잎노드인 12는 3 + 4 + 5의 결과이다. 부모노드를 기준으로 왼쪽자식노드는 $w_i$를 포함시킨다는 뜻이며 오른쪽 노드는 $w_i$를 배제한다는 의미이다.

위의 상태공간트리에서 유망하지 않은 자식노드들은 X로 표시된다. 12, 8, 9를 포함하는 노드들은 다음 무게인 6을 추가하면 weight의 값이 W를 초과하기 때문에 유망하지 않다. 7, 3, 4, 0을 포함하는 노드들은 남은 무게를 더했을때의 총합이 W까지 가기에는 충분하지 않으므로 유망하지 않다.

The Backtracking Algorithm for the Sum-of-Subsets Problem

Algorithm Design

If we sort the weights in nondecreasing order, there are obvious signs that a node is nonpromising.

부분합 문제의 상태공간트리 전체를 깊이우선탐색하는 것은 비효율적이다. $w_1$ ~ $w_n$을 오름차순으로 정렬하면 가지치기를 판단할 수 있는 분명한 증거들이 있다.

• weight: the sum of the weights that have been included up to a node at level $i$
  $$
  weight + w_{i+1} > W \text{: a node is nonpromising.}
  $$

• total: the total weight of the remaining weights
  $$
  weight + total < W \text{: a node is nonpromising.}
  $$

weight는 i레벨에 있는 노드까지 포함된 무게의 합이다. weight에 $w_{i+1}$을 더한 결과가 W를 초과한다면 그 이후에 어떤 다른 무게도 W를 넘길 것이다. 즉, $w_{i+1}$부터는 유망하지 않으므로 그 자식 노드들은 탐색대상에서 제외한다.

total은 남아있는 아이템의 총 무게이다. total에 weight를 더해서 W보다 작다면, 그 노드 아래로 확장을 해도 W와 같아질 수 없다. 따라서 이 경우도 유망하지 않으므로 가지치기를 통해 탐색대상에서 제외한다.

The algorithm uses an array include. It sets include[i] to “YES” if w[i] is to be included and to “NO” if it is not.

$w_i$의 포함여부는 include[i] 배열을 통해 관리한다. include[i]는 $w_i$를 포함하면 “YES”, 그렇지 않으면 “NO” 값을 가진다.

When the sum of the weights included up to a node equals W , there is a solution at that node. Therefore, we cannot get another solution by including more items. This means that if

$$W = weight$$

we should print the solution and backtrack.

W = weight 등식이 성립하면 해답을 출력하고 백트래킹한다.

Pseudo Code

void sum_of_subsets(index i, int weight, int total)
{
  if (promising(i))
    if (weight == W)
      cout << include[1] through include[i];
    else {
      include[i+1] = "yes"; // Include w[i+1]
      sum_of_subsets(i+1, weight + w[i+1], total - w[i+1]);
      include[i+1] = "no";  // Do not include w[i+1]
      sum_of_subsets(i+1, weight, total - w[i+1]);
    }
}

bool promising(index i)
{
  return (weight + total >= W) && (weight == W || weight + w[i+1] <= W);
}

Source Code

// File: sumofsubs.h
#include <cstring>
using namespace std; // for string

namespace algorithms
{
  void sum_of_subsets(int i, int weight, int total, int W, int* w, string* include);
  // Problem: Given n positive integers (weights) and a positive integer W,
  // determine all combinations of the integers that sum to W.
  // Inputs: positive integer n, sorted (nondecreasing order) array of positive
  // integers w indexed from 1 to n, and a positive integer W.
  // Outputs: all combinations of the integers that sum to W.

  bool promising(int i, int weight, int total, int W, int* w);

  template <typename Item>
  Item* get_vector_space(const int n)
  // Prostcondition: Return the array containing n spaces
  {
    Item* v = new Item[n];
    return (v-1); // offset the pointer
  }
}

// File: sumofsubs.cpp
#include <iostream>
#include <iomanip> // Provides setw
#include "sumofsubs.h"

namespace algorithms
{
  void sum_of_subsets(int i, int weight, int total, int W, int* w, string* include)
  {
    if (promising(i, weight, total, W, w))
    {
      if (weight == W)
      {
        for (int j = 1; j <= i; ++j)
          cout << setw(3) << "w" << j << ": " << include[j] << setw(3);
        cout << endl;
      }
      else
      {
        include[i + 1] = "YES"; // Include w[i+1]
        sum_of_subsets(i + 1, weight + w[i + 1], total - w[i + 1], W, w, include);
        include[i + 1] = "NO "; // Do not include w[i+1]
        sum_of_subsets(i + 1, weight, total - w[i + 1], W, w, include);
      }
    }
  }

  bool promising(int i, int weight, int total, int W, int *w)
  {
    return (weight + total >= W) && (weight == W || weight + w[i + 1] <= W);
  }
}

// File: sumofsubstest.cpp
#include <iostream>
#include <cstdlib> // Provides EXIT_SUCCESS
#include "sumofsubs.h"
using namespace algorithms;

int main( )
{
  const int N = 5;
  const int W = 21;
  int* w = get_vector_space<int>(N);
  int total = 0;
  string* include = get_vector_space<string>(N);

  w[1] = 5;
  w[2] = 6;
  w[3] = 10;
  w[4] = 11;
  w[5] = 16;

  // total 초기값 계산
  for (int i = 1; i <= 5; ++i)
  	total += w[i];

  sum_of_subsets(0, 0, total, W, w, include);

  delete [ ] (w + 1);
  delete [ ] (include + 1);

  return EXIT_SUCCESS;
}

Time Complexity Analysis

Worst-Case Time Complexity

• $O(n) = 1 + 2 + 2^2 + 2^3 + … + 2^n = 2^{n+1} - 1 \in \Theta(2^n)$

As stressed before, even though the worst case is exponential, the algorithm can be efficient for many large instances.

$w_i$를 포함시키느냐 그렇지 않느냐의 두 가지 선택이므로 상태공간트리 내 전체 노드의 수는 최대 $2^{n+1} - 1$개가 된다. 최악의 경우가 지수이지만, 가지치기를 통해 상태노드의 수를 줄일 수 있기 때문에 알고리즘의 효율은 더 좋을 수 있다.

n-퀸 문제와 마찬가지로 유망한 노드의 수를 정확히 구하기 위한 방법은 실제 알고리즘을 수행 후 구축된 상태공간트리의 노드 갯수를 세어 보는 수 밖에 없다. 또한 몬테 카를로 알고리즘을 이용해 시간복잡도를 추정할 수 있다.